//给定一个数字，我们按照如下规则把它翻译为字符串：0 翻译成 “a” ，1 翻译成 “b”，……，11 翻译成 “l”，……，25 翻译成 “z”。一个数字可
//能有多个翻译。请编程实现一个函数，用来计算一个数字有多少种不同的翻译方法。 
//
// 
//
// 示例 1: 
//
// 输入: 12258
//输出: 5
//解释: 12258有5种不同的翻译，分别是"bccfi", "bwfi", "bczi", "mcfi"和"mzi" 
//
// 
//
// 提示： 
//
// 
// 0 <= num < 2³¹ 
// 
// Related Topics 字符串 动态规划 👍 449 👎 0

package leetcode.editor.cn;
//leetcode submit region begin(Prohibit modification and deletion)
class SolutionOffer46 {
    /**
     * 可用变量优化滚动数组
     * @param num
     * @return
     */
    public int translateNum1(int num) {
        String s = String.valueOf(num);
        if(s.length() <= 1) return s.length();
        int[] dp = new int[s.length()+1];
        dp[0] = 1;
        dp[1] = 1;
        //这样初始化太麻烦，下标可以从0开始
//        if(Integer.parseInt(s.substring(0,2)) > 25){
//            dp[1] = 1;
//        } else {
//            dp[1] = 2;
//        }
        for(int i = 2; i <= s.length(); i++){
            if(s.substring(i-2,i).compareTo("25") > 0 || s.substring(i-2,i).compareTo("10") < 0){
                dp[i] = dp[i-1];
            } else {
                dp[i] = dp[i-1]+dp[i-2];
            }
        }
        return dp[s.length()];
    }

    /**
     * 递归
     * @param num
     * @return
     */
    public int translateNum(int num){
        String s = String.valueOf(num);
        return dfs(s,0);
    }

    private int dfs(String s, int index) {
        if(index == s.length()) return 1;
        if(s.substring(index,index+2).compareTo("10") >= 0 && s.substring(index,index+2).compareTo("25") <= 0){
            return dfs(s,index+1)+dfs(s,index+2);
        } else {
            return dfs(s,index+1);
        }
    }

    public static void main(String[] args) {
        new SolutionOffer46().translateNum(12258);
    }
}
//leetcode submit region end(Prohibit modification and deletion)
